/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/convert-sorted-list-to-balanced-bst
   @Language: C++
   @Datetime: 16-02-09 05:46
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

// Method 1, Recursion, Time 95ms
class Solution {
	TreeNode *list2BST(ListNode *head,int len){
		if (head==NULL || len==0) return NULL;
		ListNode *mid = head;
		for(int i=len>>1; i--; mid=mid->next);
		TreeNode *root = new TreeNode(mid->val);
		root->left = list2BST(head,len>>1);
		root->right = list2BST(mid->next,len-(len>>1)-1);
		return root;
	}

public:
	/**
	 * @param head: The first node of linked list.
	 * @return: a tree node
	 * Tip: traversal by preorder
	 *      find middle of list node mid
	 *      build mid to tree root
	 *      recurse build left and right
	 */
	TreeNode *sortedListToBST(ListNode *head) {
		// write your code here
		int len = 0;
		for(ListNode *i=head; i; ++len,i=i->next);
		return list2BST(head,len);
	}
};

// Method 2, secondary pointer, Time 125ms
class Solution {
	TreeNode *list2BST(ListNode **pnode, int len) {
		if (len==0) return NULL;
		TreeNode *left = list2BST(pnode,len>>1);
		TreeNode *root = new TreeNode((*pnode)->val);
		*pnode = (*pnode)->next;    // redirect to next node
		root->left = left;
		root->right = list2BST(pnode,len-(len>>1)-1);
		return root;
	}
	
public:
	/**
	 * @param head: The first node of linked list.
	 * @return: a tree node
	 * Tip : traversal by inorder
	 */
	TreeNode *sortedListToBST(ListNode *head) {
		int len = 0;
		for(ListNode *p=head; p; ++len,p=p->next);
		return list2BST(&head,len);
	}
};
